/*
 * @Author: wwssaabb
 * @Date: 2021-12-14 16:24:30
 * @LastEditTime: 2021-12-14 18:02:48
 * @FilePath: \handwritten-code\algorithm\多数元素.js
 */

/* 
给定一个大小为 n 的数组， 找到其中的多数元素。 多数元素是指在数组中出现次数 大于⌊ n / 2⌋ 的元素。
你可以假设数组是非空的， 并且给定的数组总是存在多数元素。

示例 1：
输入：[3, 2, 3]
输出： 3

示例 2：
输入：[2, 2, 1, 1, 1, 2, 2]
输出： 2

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/majority-element
*/

//object
var majorityElement = function (nums) {
  if (nums.length === 1) return nums[0]
  let target = nums[0],
    max = 0,
    record = {},
    limit = nums.length >> 1
  for (let i = 0; i < nums.length; i++) {
    if (record[nums[i]]) {
      record[nums[i]]++
      if (record[nums[i]] > max) {
        max = record[nums[i]]
        target = nums[i]
      }
    } else {
      record[nums[i]] = 1
    }
    if (max > limit) return target
  }
}


//排序，时间O(nlogn),空间O(1)
var majorityElement = function (nums) {
  return nums.sort((x, y) => x - y)[nums.length >> 1]
}

console.log(majorityElement([1]))
console.log(majorityElement([1, 1]))
console.log(majorityElement([1, 2, 2]))
console.log(majorityElement([3, 2, 3]))
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]))
console.log(majorityElement([1, 7, 2, 7, 3, 7, 4, 7, 5, 7]))